//https://leetcode.cn/problems/minimum-moves-to-spread-stones-over-grid/description/?envType=daily-question&envId=2024-07-20


class Solution {
    int ans = INT_MAX;
public:
    int minimumMoves(vector<vector<int>>& grid) {
        vector<pair<int, int>>zeros, onesMore;
        for(int i = 0;i < grid.size();i++){
            for(int j = 0;j < grid[0].size();j++){
                if(grid[i][j] == 0){
                    zeros.emplace_back(i, j);
                }
                else if(grid[i][j] > 1){
                    onesMore.emplace_back(i, j);
                }
            }
        }
        dfs(zeros, onesMore, grid, 0, 0);

        return ans;
    }
    void dfs(vector<pair<int, int>>& zeros, vector<pair<int, int>>&onesMore, vector<vector<int>>& grid, int m, int operation){
        if(m >= zeros.size()){
            ans = min(ans, operation);
            return;
        } 
        for(int i = 0;i < onesMore.size();i++){
            auto[x1, y1] = onesMore[i];
            auto[x2, y2] = zeros[m];
            if(grid[x1][y1] > 1){
                grid[x1][y1]--;
                int add = abs(x1 - x2) + abs(y1 - y2);
                dfs(zeros, onesMore, grid, m + 1, operation + add);
                grid[x1][y1]++;
            }
        }
    }
};